import java.util.*;

class Solution2 {
    public int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<Character>();
        int n = s.length();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.remove(s.charAt(i - 1));
            }
            while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                // 不断地移动右指针
                occ.add(s.charAt(rk + 1));
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = Math.max(ans, rk - i + 1);
        }
        return ans;
    }
}

class MySolution1 {
    public List<String> letterCombinations(String digits) {
        List<String> arrayList = new ArrayList<String>();
        if (digits.length() == 0) {
            return arrayList;
        }
        Map<Character, String> hashMap = new HashMap<Character, String>();
        hashMap.put('2', "abc");
        hashMap.put('3', "def");
        hashMap.put('4', "ghi");
        hashMap.put('5', "jkl");
        hashMap.put('6', "mno");
        hashMap.put('7', "pqrs");
        hashMap.put('8', "tuv");
        hashMap.put('9', "wxyz");
        combination(arrayList, hashMap, digits, 0, new StringBuffer());
        return arrayList;
    }
    public void combination(List<String> arrayList, Map<Character, String> hashMap, String digits,
                            int index, StringBuffer cache) {
        if (index == digits.length()) {
            arrayList.add(cache.toString());
        } else {
            char c = digits.charAt(index);
            String str = hashMap.get(c);
            for (int i = 0; i < str.length(); i++) {
                cache.append(str.charAt(i));
                combination(arrayList, hashMap, digits, index + 1, cache);
                cache.deleteCharAt(index);
            }
        }
    }
}

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> combinations = new ArrayList<String>();
        if (digits.length() == 0) {
            return combinations;
        }
        Map<Character, String> phoneMap = new HashMap<Character, String>() {{
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }};
        backtrack(combinations, phoneMap, digits, 0, new StringBuffer());
        return combinations;
    }

    // 返回对象，哈希表，素材字符串对象，整型，可变字符串对象
    public void backtrack(List<String> combinations, Map<Character, String> phoneMap, String digits,
                          int index, StringBuffer combination) {
        if (index == digits.length()) {
            // 当次排列已达到尽头，组合完成，传递给最终容器；
            combinations.add(combination.toString());
        } else {
            // 获取到素材字符串中当前所指的字符（数字）
            char digit = digits.charAt(index);

            // 通过获取到的字符（数字）进行查询，获取到字符（数字）所对应的字符串
            String letters = phoneMap.get(digit);

            // 获取 所得到字符串 的长度
            int lettersCount = letters.length();

            for (int i = 0; i < lettersCount; i++) {
                // 获取 所得字符串中 当前 i 所指向的字符，存入临时字符串容器（缓存区）
                combination.append(letters.charAt(i));

                // 将index索引后进一位，进行组合
                backtrack(combinations, phoneMap, digits, index + 1, combination);

                // 删除当前指引所指向的字符，分次清理字符串容器（分次清理缓存）
                combination.deleteCharAt(index);
            }
        }
    }
}
